home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d12 / cgazv5n5.arc / LZW2.C < prev    next >
C/C++ Source or Header  |  1991-09-23  |  7KB  |  179 lines
  1. /*--- LZW2.C ----------------------------- Listing 3 ----
  2. * Contents:  This is the decompression portion of
  3. *            the LZW data compression program.  It
  4. *            contains the following routines:
  5. *                decompression_routine
  6. *                read_compressed_file
  7. *                output_character
  8. *                code_not_present
  9. *                new_code
  10. *                next_symbol
  11. *                push_onto_stack
  12. *                pop_off_of_stack
  13. *                put_into_table
  14. *
  15. * Author:  Dwayne Phillips
  16. * Compiler: Microsoft C 6.0a, BC++ 2.0
  17. *           Note: Must link with at least an 8K stack
  18. * Switches: DEBUG - if defined, debugging data is shown
  19. *           STATS - if defined, statistics are given
  20. * Date: February 1991
  21. * May be used freely if authorship is acknowledged
  22. *-------------------------------------------------------*/
  23. #include "lzw.h"
  24.  
  25. /*--------------------------------------------------------
  26.  * This is the main routine for the decompression process.
  27.  *------------------------------------------------------*/
  28. void decompression_routine( table_item *string_table,
  29.                             FILE *infile, FILE *outfile )
  30. {
  31.     int k, last_k, already_entered;
  32.     code_type in_buffer[IB_LENGTH_D], w_code, last_code;
  33.     unsigned table_max;
  34.     unsigned  in_counter, out_counter, codes_read;
  35.     unsigned char out_buffer[OB_LENGTH_D];
  36.     unsigned char w[100], w2[100];
  37.     unsigned i, j;
  38.  
  39.     /* start up */
  40.     out_counter = 0;
  41.     table_max = initialize ( string_table );
  42.     codes_read = read_compressed_file ( in_buffer, infile );
  43.  
  44.     /* process first code now */
  45.     SHOW( printf ( "\nIn: %d", in_buffer[0] ); )
  46.     k = last_k = string_table[in_buffer[0]].character;
  47.     output_char ( k, out_buffer, &out_counter, outfile );
  48.     create_string ( w, k );
  49.     w_code = last_code = k;
  50.     in_counter = 1;
  51.     already_entered = 0;
  52.  
  53.     for (;;) {
  54.         for ( ; in_counter < codes_read; in_counter++ ) {
  55.             code_type ct;
  56.  
  57.             SHOW( printf( "\nIn: %d", in_buffer[in_counter]); )
  58.             if ( in_buffer[in_counter] > table_max ) {
  59.                 /* A code that we don't know yet. We must infer
  60.                    what the compression routine saw... */
  61.                 put_wk_in_table ( last_code, last_k,
  62.                                   string_table, &table_max);
  63.                 already_entered = 1;
  64.                 create_string(w, last_k);
  65.                 w_code = last_k;
  66.                 SHOW( { unsigned char *s; printf ( " w: '" ); )
  67.                 SHOW( for (s = w; *s; s++)
  68.                       printf( isprint(*s) ? "%c" : " %dd ", *s);)
  69.                 SHOW( printf ( "'" ); } )
  70.             }
  71.             if ( in_buffer[in_counter] > table_max ) {
  72.                  printf ( "\nInternal error #1\n" );
  73.                  fclose ( infile );
  74.                  fclose ( outfile );
  75.                  exit ( 1 );
  76.             }
  77.  
  78.             /* save for later */
  79.             last_code = in_buffer[in_counter];
  80.             ct = string_table[in_buffer[in_counter]].num;
  81.             k = last_k =
  82.                 string_table[in_buffer[in_counter]].character;
  83.             if ( k == 0 ) {
  84.                 output_char ( 0, out_buffer,
  85.                               &out_counter, outfile);
  86.                 update_table( 0, w, &w_code,
  87.                               string_table, &table_max );
  88.             }
  89.             else {
  90.                 w2[0] = '\0';
  91.                 build_string ( w2, ct, string_table );
  92.                 append_char ( w2, k );
  93.                 j = strlen ( w2 );
  94.                 last_k = *w2;
  95.                 for ( i = 0; i < j; i++ ) {
  96.                     output_char( w2[i], out_buffer,
  97.                                  &out_counter, outfile );
  98.                     if ( !already_entered )
  99.                         update_table ( w2[i], w, &w_code,
  100.                                    string_table, &table_max );
  101.                     already_entered = 0;
  102.                 }
  103.             }
  104.         }
  105.  
  106.         /* get another block */
  107.         if ( feof ( infile ))
  108.              break;
  109.         codes_read = read_compressed_file ( in_buffer, infile );
  110.         in_counter = 0;
  111.     }
  112.     /* flush partial buffer */
  113.     if ( out_counter != 0 )
  114.         my_write ( outfile, out_buffer, 1, out_counter );
  115.     SHOW( print_string_table (string_table,
  116.             "DONE", BASE_TABLE+1, table_max ); )
  117. #if defined(STATS)
  118.     printf ( "Table had %d entries at conclusion.\n",
  119.              table_max );
  120.     printf ( "Input file was %ld bytes.\n", ftell (infile ));
  121.     printf ( "Output file is %ld bytes.\n", ftell (outfile ));
  122.     #endif
  123. }
  124.  
  125. /*-----------------------------------------------------------
  126.  * keep string_table updated
  127.  *---------------------------------------------------------*/
  128. void update_table( int k, unsigned char *w, code_type *w_code,
  129.                    table_item *string_table, unsigned *table_max)
  130. {
  131.     code_type wk;
  132.  
  133.     if ( k == '\0' ||   /* NULLs are special */
  134.        ( wk = wk_is_in_table ( w, k, string_table )) == 0) {
  135.         if ( k != '\0' && strlen ( w ) != 0 )
  136.             put_wk_in_table ( *w_code, k,
  137.                             string_table, table_max );
  138.         create_string ( w, k );
  139.         *w_code = k;
  140.     }
  141.     /* wk is a known code, so note what we've found */
  142.     else {
  143.         append_char ( w, k );
  144.         *w_code = wk;
  145.     }
  146.     SHOW( { unsigned char *s; printf ( " w: '" ); )
  147.     SHOW( for ( s = w; *s; s++ )
  148.           printf ( isprint ( *s ) ? "%c" : " %dd ", *s ); )
  149.     SHOW( printf ( "'" ); } )
  150. }
  151.  
  152. /*-------------------------------------------------------
  153.  * read the type short from the compressed file.
  154.  *------------------------------------------------------*/
  155. unsigned read_compressed_file ( code_type *inbuf, FILE *infile )
  156. {
  157.     return my_read ( infile, inbuf,
  158.                      sizeof ( code_type ), IB_LENGTH_D );
  159. }
  160.  
  161. /*-------------------------------------------------------
  162.  * output the character k. It puts it in the output buffer.
  163.  * If the output buffer is full it writes the buffer to
  164.  * the output file.
  165.  *------------------------------------------------------*/
  166. void output_char( int k, unsigned char *out_buffer,
  167.                   unsigned *out_counter,
  168.                   FILE *outfile )
  169. {
  170.     if ( *out_counter >= OB_LENGTH_D ){
  171.         my_write ( outfile, out_buffer, 1, *out_counter );
  172.         *out_counter = 0;
  173.     }
  174.  
  175.     SHOW( printf ( isprint ( k ) ? " Out: '%c'" :
  176.                                    " Out: '%dd'", k); )
  177.     out_buffer[*out_counter] = (unsigned char) k;
  178.     *out_counter += 1;
  179. } /* ends output_character */